//在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 
//
// 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 
//
// 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。 
//
// 说明: 
//
// 
// 如果题目有解，该答案即为唯一答案。 
// 输入数组均为非空数组，且长度相同。 
// 输入数组中的元素均为非负数。 
// 
//
// 示例 1: 
//
// 输入: 
//gas  = [1,2,3,4,5]
//cost = [3,4,5,1,2]
//
//输出: 3
//
//解释:
//从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
//开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
//开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
//开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
//开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
//开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
//因此，3 可为起始索引。 
//
// 示例 2: 
//
// 输入: 
//gas  = [2,3,4]
//cost = [3,4,3]
//
//输出: -1
//
//解释:
//你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
//我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
//开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
//开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
//你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
//因此，无论怎样，你都不可能绕环路行驶一周。 
// Related Topics 贪心 数组 
// 👍 807 👎 0

package com.cute.leetcode.editor.cn;
public class GasStation {
    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        new GasStation().new Solution().canCompleteCircuit(gas, cost);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 说明：若题目有解，则答案是唯一的
         */
        public int canCompleteCircuit1(int[] gas, int[] cost) {
            int len = gas.length;
            for (int index = 0; index < len; index++) {
                //这里是在找合适的初始位置，没有这一步的话有一个案例会超时
                //好家伙，单独循环寻找的时间比这样写执行时间更短
                if (gas[index] == 0) continue;
                int rest = gas[index]-cost[index];
                int i = index+1;
                while (rest >= 0){
                    if (i == len) i = 0;
                    if (i == index) return index;
                    rest += gas[i] - cost[i];
                    i++;
                }
            }
            return -1;
        }


        /**
         * 直接从全局最优的角度去解决问题
         * 从0开始遍历所有数组，得到总燃油量的差值，以及油箱中差值的最小值
         * 如果差值 < 0说明无法到达
         * 如果总燃油差值>0，说明一定可以访问一圈
         *      1.如果从0开始遍历的时候，油箱中最小差值>=0，那么说明从0出发即可实现
         *      2.如果差值最小值<0，那就从后向前遍历，直到差值>=0的时候，就是出发的位置了
         *      3.其实这里是可以优化的，如果找到min值，且能走完的话，那起始位置一定是min的下一处
         *      因为一定能走完的话，差值最大的下一个位置一定能将所有损失都找回来
         */
        public int canCompleteCircuit2(int[] gas, int[] cost) {
            int sum = 0;
            int min = Integer.MAX_VALUE;
            int len = gas.length;
            int index = 0;
            for (int i = 0; i < len; i++) {
                sum += gas[i]-cost[i];
                if (sum < min && sum < 0) {
                    min = sum;
                    index = i;
                }
            }
            return sum < 0 ? -1 :(index + 1) % len;
        }

        /**
         * 贪心算法：从局部最优推导全局最优
         * 遍历的时候记录全部差值以及当前区间差值
         * 如果当前区间差值<0，那么起始位置一定不在当前区间内
         *
         */
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int start = 0;
            int curSum = 0;
            int sum = 0;
            int len = cost.length;
            for (int i = 0; i < len; i++) {
                int diff = gas[i] - cost[i];
                sum += diff;
                curSum += diff;
                if (curSum < 0){
                    start = i+1;
                    curSum = 0;
                }
            }
            if (sum < 0) return -1;
            return start;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}





































